package nqueens.algorithm;

public class BacktrackingAlgorithm extends Algorithm {

    private boolean solutionFound = false;

    /**
     * Constructor which does not work correctly at present.
     * @param valiateSolutions flag to validate the solutions
     */
    public BacktrackingAlgorithm(boolean valiateSolutions) {
        super(valiateSolutions);
    }

    @Override
    protected void solve(int N) throws InterruptedException {
        solutionFound = false;
        int[] queen = new int[N];
        solve(queen, 0);       
    }

    /**
     * This validates the placement of the last queen
     * @param queen the array of queens
     * @param N The size of the problem set
     * @return a boolean representing whether or not this is a valid placement
     * @throws InterruptedException an interrupt was caught and needs to bubble back to the run method
     */
    public boolean isConsistent(int[] queen, int N) throws InterruptedException {
        for (int i = 0; i < N; i++) {
            if (queen[i] == queen[N]) {
                return false;   // column
            }
            if ((queen[i] - queen[N]) == (N - i)) {
                return false;   // major
            }
            if ((queen[N] - queen[i]) == (N - i)) {
                return false;   // minor
            }
        }
        return true;
    }

    /**
     * Private helper method for solving the puzzle.
     * @param queen the array of queens
     * @param N the input size
     * @throws InterruptedException an interrupt was caught and needs to bubble back to the run method
     */
    private void solve(int[] queen, int N) throws InterruptedException {
        int queenLength = queen.length;
        if (N == queenLength && solutionFound == false) {
            setChessBoard(convertToChessBoard(queen));
            if (validateSolution()) {
                setLastSolutionSolved(getChessBoard());
                solutionFound = true;
            }
        } else if (solutionFound == false) {
            for (int ii = 0; ii < queenLength; ii++) {
                queen[N] = ii;
                if (isConsistent(queen, N)) {
                    solve(queen, N + 1);
                }
            }
        }
    }
}